package stmo.树.查找树;


/**
 *      2-3查找树
 *
 *
 */
public class In2O3Tree {

/**
 *   一棵2-3查找树要么为空，要么满足满足下面两个要求：
 *
 *   2-结点：
 *   含有一个键(及其对应的值)和两条链，左链接指向2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。
 *
 *   3-结点：
 *   含有两个键(及其对应的值)和三条链，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个
 *   键之间，右链接指向的2-3树中的键都大于该结点。
 *
 *   查找
 *   将二叉查找树的查找算法一般化我们就能够直接得到2-3树的查找算法。要判断一个键是否在树中，我们先将它和根结点中的键比较。
 *   如果它和其中任意一个相等，查找命中；否则我们就根据比较的结果找到指向相应区间的连接，并在其指向的子树中递归地继续查找。
 *   如果这个是空链接，查找未命中。
 *
 *    向2-结点中插入新键
 *    只需要将新的元素放到这个2-结点里面使其变成一个3-结点即可。
 *
 *    向一棵只含有一个3-结点的树中插入新键
 *    我们将这个4-结点的中间元素提升，左边的键作为其左子结点，右边的键作为其右子结点。
 *
 *    向一个父结点为2-结点的3-结点中插入新键
 *    我们将这个4-结点的中间元素提升，左边的键作为其左子结点，右边的键作为其右子结点。父节点从2-结点变为3-结点
 *
 *    向一个父结点为3-结点的3-结点中插入新键
 *    当我们插入的结点是3-结点的时候，我们将该结点拆分，中间元素提升至父结点，但是此时父结点是一个3-结点，插入之后，
 *    父结点变成了4-结点，然后继续将中间元素提升至其父结点，直至遇到一个父结点是2-结点，然后将其变为3-结点，不需要
 *    继续进行拆分。
 *
 *    分解根结点
 *    当插入结点到根结点的路径上全部是3-结点的时候，最终我们的根结点会编程一个临时的4-结点，此时，就需要将根结点拆分
 *    为两个2-结点，树的高度加1。
 *
 *     2-3树的性质
 *     一棵完全平衡的2-3树具有以下性质：
 *     1.任意空链接到根结点的路径长度都是相等的。
 *     2. 4-结点变换为3-结点时，树的高度不会发生变化，只有当根结点是临时的4-结点，分解根结点时，树高+1。
 *     3. 2-3树与普通二叉查找树最大的区别在于，普通的二叉查找树是自顶向下生长，而2-3树是自底向上生长。
 *
 */

}
